class Solution:
    def maximalSquare(self, matrix) -> int:
        if not matrix or len(matrix) == 0 or len(matrix[0]) == 0:
            return 0
        
        maxSide = 0
        rows, columns = len(matrix), len(matrix[0])

        dp = [[0] * columns for _ in range(rows)]

        for i in range(rows):
            for j in range(columns):
                if matrix[i][j] == '1':
                    dp[i][j] = 1 if i == 0 or j == 0 else min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1
                    maxSide = max(maxSide, dp[i][j])

        
        return maxSide * maxSide



if __name__ == '__main__':
    s = Solution()
    matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
    print(s.maximalSquare(matrix))
    